import java.util.HashMap;

public class IntersectingLinkedList {

    public static void main(String[] args) {
        Node node1 = new Node(7, null);
        Node node2 = new Node(9, node1);
        Node node3 = new Node(5, node2);
        Node node4 = new Node(4, node3);
        Node node5 = new Node(5, node4);

        Node node6 = new Node(1, null);
        Node node7 = new Node(2, node6);
        Node node8 = new Node(3, node7);
        Node node9 = new Node(4, node8);
        Node node10 = new Node(5, node9);
        Node intersectionNode = getIntersectionNode(node5, node10);
        if (intersectionNode != null) {
            System.out.println(intersectionNode.value);
        } else {
            System.out.println("No intersection");
        }

    }

    public static Node getIntersectionNode(Node n1, Node n2) {
        if (n1 == null || n2 == null) {
            return null;
        }
        Node p1 = n1;
        Node p2 = n2;
        int count = 0;
        while (p1 != p2) {
            p1 = p1.next;
            p2 = p2.next;
            if (p1 == null) {
                p1 = n2;
                count++;
            }
            if (p2 == null) {
                p2 = n1;
                count++;
            }
            // 如果两个指针都已经遍历完两个链表，说明没有交点
            if (count > 2) {
                return null;
            }
        }
        return p1;
    }


    private static class Node {
        int value;
        Node next;

        public Node(int value, Node next) {
            this.value = value;
            this.next = next;
        }
    }
}